Computer-implemented data storage systems typically comprise various types of data storage in which data is stored on behalf of host computer systems. Storage controls control access to data storage media and memories in response to read and write requests. The storage controls may direct the data in accordance with data storage memories and devices such as cache, non-volatile storage, RAID (redundant array of independent disks), JBOD (just a bunch of disks), etc. arranged into various redundancy, access speed and security levels.
As an example, an International Business Machines Corp. (IBM®) ESS (Enterprise Storage Server) such as a DS8000™ has redundant clusters of computer entities, cache memories, non-volatile storage, etc., called “central electronics complexes” or “CECs”.
Within a data storage system, fast memories may be employed as cache used to store data or instructions that were accessed recently, are accessed frequently, or are likely to be accessed in the near future. Data stored in cache memories can be accessed quickly instead of being fetched or recomputed, saving both time and resources.
Cache memories can be provided in multiple levels. For example, a cache data storage system may comprise both a “first” or “primary” cache memory and a “secondary” cache memory. Typically, the first cache memory has faster access and is more costly per unit of data than a secondary cache memory, and the secondary cache memory has greater storage capacity than the first cache memory. For example, a first cache memory comprises DRAM (“dynamic random access memory”), while the secondary cache comprises flash memory solid-state drives (SSDs) such as “Flash_Cache” (TM International Business Corp.). When accessing data, a computing system or device may first look for data in the first cache memory and, if the data is not present there, look for the data in the secondary cache memory. When data is not available in either memory, it typically is accessed from the major data storage which comprises slower access speed data storage such as RAID, JBOD, etc. When data is read, it typically remains in the major data storage and is copied to the first cache memory and/or the secondary cache memory. If read data in the first cache memory is not accessed promptly or frequently, it may be demoted to the secondary cache memory or evicted. If read data in the secondary cache memory is not accessed promptly or frequently, it may be evicted. When writing data, a computing system or device may write data to the first cache memory. If write data in the first cache is not accessed promptly or frequently, this data may be demoted to the secondary cache memory. If data is not accessed promptly or frequently from the secondary cache memory, it may be demoted to the slower access speed data storage such as RAID, JBOD, etc. Alternatively, write data may be written to the major data storage as soon as possible after being received by the data storage system.
Typically, a LRU (least recently used) algorithm is employed to demote data to the next lower level or to evict data from the first cache memory or the secondary cache memory.
In some memories, such as a secondary cache memory, the data is stored in log-structured fashion (written sequentially, requiring a log to determine where data is stored on a logical basis) as pages in large extents of data. The data pages are reviewed under a LRU algorithm, and the least recently used pages are invalidated. To reclaim space, the system will select the log-structured extents (LSEs) that have the most invalidated pages and compact the valid pages, relocating them in new LSEs, leaving one or more LSEs free. The relocations incur a large number of I/O (input/output) relocation operations, as many LSEs need to be read and one or more LSEs written at each iteration of the reclamation process.